Linearizability Violations in Cassandra

It is important to note that operations on a single row are not linearizable by default, even when using majority quorums.

To understand why it is useful to learn how Cassandra handles partial failures and network delays. Let’s examine two different scenarios.

Without read repair#

In this scenario, we assume that read repair is not used. The system consists of three different replicas with a single row that contains a single column owner with the value none.

Client A initially performs a write operation to set owner = A. While this operation is in progress, two clients B and C perform a read operation for the owner in sequence. The majority quorum of client B contains one replica that has already received the write operation, while client C contacts a quorum with nodes that haven’t received it yet. As a result, client B reads owner = A, while client C reads owner = none even though the operation from the latter started after the operation from the former had been completed, which violates linearizability.

The following illustration shows this phenomenon:

With read repair#

The violation of linearizability in the previous example would be eliminated if read repair was used since the read from client B would propagate the value to replica 2, and client C would also read owner = A.

So, let’s assume that read repair is used and examine a different scenario. Client A performs a write operation again to set owner = A. The write succeeds in one replica and fails in the other replica. As a result, the write is considered unsuccessful, and the coordinator returns a failure response back to the client. Afterward, client B performs a read operation that uses a quorum that contains the replica where the previous write succeeded.

Cassandra performs a read repair using the LWW strategy, thus propagating the value to replica 2. Consequently, a write operation that failed has affected the state of the database, thus violating linearizability. This example is shown in the following illustration: